package leetcode.ArrayAndString;

import java.util.Arrays;

public class ArrayPairSum {

    /**
     * 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对
     * 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
     * @param nums
     * @return
     */

    public static int arrayPairSum(int[] nums) {
        int length = nums.length;
        int sum = 0;
        Arrays.sort(nums);

        for (int i = 0; i <length-1 ; i = i+2) {
            sum += nums [i];

        }
        return sum;
    }

    // 可以用桶排序加速 int[20001]
    public int betterArrayPairSum(int[] nums){
        int[] a = new int[20001];
        int sum = 0;

        for(int i=0; i<nums.length; i++){
            a[nums[i] + 10000]++;
        }

        boolean even = false;
        for(int i=0; i<a.length; i++){
            while(a[i] > 0){
                if(!even){
                    sum += i - 10000;
                }
                even = !even;
                a[i]--;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 4, 2};
        System.out.println(arrayPairSum(nums));
    }


}
